package tree

import (
	// "errors"
	"fmt"
)

// RB树 红黑树
// 红黑树相较于avl树，有个旋转次数少的有点，适合插入、删除操作较多的业务，相对的，搜索较多的业务更适用于avl树
// 红黑树五个要点：
// 1.每个节点非黑即红
// 2.根节点是黑色
// 3.空节点是黑色
// 4.红节点的子节点必须是黑色
// 5.从节点到其子孙节点的所有路径上包含的黑色节点含有相同数目
// 满足以上特性，即是一颗红黑树
// 让 Red = true 、 Black = false

const(
	Red = true
	Black = false
)
type RBTree struct{
	RoB bool
	Value interface{}
	LChild *RBTree
	RChild *RBTree
}

func NewRBTree()*RBTree{
	return &RBTree{RoB: true} // 默认是红色
}

// 二叉树接口实现 ----------------------
func (rb *RBTree)GetLeftChild()BinTree{
	if rb.LChild == nil {
		return nil
	}
	return rb.LChild
}

func (rb *RBTree)SetLeftChild(node BinTree){
	if node == nil {
		rb.LChild = nil
	}else{
		rb.LChild, _ = node.(*RBTree)
	}
}

func (rb *RBTree)GetRightChild()BinTree{
	if rb.RChild == nil {
		return nil
	}
	return rb.RChild
}

func (rb *RBTree)SetRightChild(node BinTree){
	if node == nil {
		rb.RChild = nil
	}else{
		rb.RChild, _ = node.(*RBTree)
	}
}

func (rb *RBTree)GetData()interface{}{
	return rb.Value
}

// 二叉树接口实现 ^^^^^^^^^^^^^^^^^^^^^^

// 叶子节点默认为黑色
func (rb *RBTree)GetColor()bool{
	if rb == nil {
		return Black
	}
	return rb.RoB
}

func (rb *RBTree)SetColor(rob bool){
	rb.RoB = rob
}

func (rb *RBTree)String()string{
	return fmt.Sprintf("RB:%v V:%v S:%p L:%p R:%p\n", rb.GetColor(), rb.Value, rb, rb.LChild, rb.RChild)
}

func (rb *RBTree)Insert(node *RBTree)*RBTree{
	root := RBTreeInsert(rb, node)
	if root.GetColor() {
		root.SetColor(Black)
	}
	return root
}

func (rb *RBTree)HandleBF()*RBTree{
	return RBTreeHandleBF(rb)
}

func RBTreeInsert(root, node *RBTree)(*RBTree){
	// 插入节点是否是root ， 是则改为黑色插入，退出
	if node == nil {
		return root
	}
	res , err := Compare(root, node)
	if err != nil {
		return nil
	}
	switch res {
	case -1 :
		if root.RChild == nil {
			root.RChild = node
		}else{
			root.RChild = RBTreeInsert(root.RChild, node)
		}
		
	case 0  :
		return root
	case 1  :
		if root.LChild == nil {
			root.LChild = node
		}else{
			root.LChild = RBTreeInsert(root.LChild, node)
		}	
	}
	//检查红黑条件
	return root.HandleBF()
}

// func RBTreeDelete(root *RBTree, data interface{})(*RBTree, error){
// 	if data == nil {
// 		return root, errors.New("data is nil")
// 	}
// 	node := NewRBTree()
// 	node.Value = data
// 	res , err := Compare(root, node)
// 	if err != nil {
// 		return root, err
// 	}
// 	switch res {
// 	case -1 :
// 		if root.RChild == nil {
// 			return root, errors.New("Can't find data")
// 		}else{
// 			root.RChild , err = RBTreeDelete(root.RChild, data)
// 			return root, err
// 		}	
// 	case 0  :
// 		return root , nil
// 	case 1  :
// 		if root.LChild == nil {
// 			return root, errors.New("Can't find data")
// 		}else{
// 			root.LChild, err  = RBTreeDelete(root.LChild, data)
// 			return root, err
// 		}	
// 	}
// 	return root.HandleBF() , nil
// }

func RBTreeHandleBF(node *RBTree)*RBTree{
	// case1 子节点为红色， 有一个孙子节点为红色
	if node.LChild.GetColor() && node.RChild.GetColor() {
		if node.LChild.LChild.GetColor() ||
			node.LChild.RChild.GetColor() ||
			node.RChild.LChild.GetColor() ||
			node.RChild.RChild.GetColor(){
				return Case1Handle(node)
			}
	}
	if node.LChild.GetColor() && !node.RChild.GetColor() {
		//左红右黑
		if node.LChild.LChild.GetColor() {
			//左孙子为红 LL型 
			return node.LLRotation()
		}else if node.LChild.RChild.GetColor(){
			//右孙子为红 LR型 
			return node.LRRotation()
		}
	}else if !node.LChild.GetColor() && node.RChild.GetColor(){
		//左黑右红
		if node.RChild.LChild.GetColor(){
			//左孙子为红 RL型
			return node.RLRotation()
		}else if node.RChild.RChild.GetColor() {
			//右孙子为红 RR型
			return node.RRRotation() 
		}
	}
	return node
}

// case1 子节点为红色，子节点的孩子有红色
//         root.?                root.r
//        /     \                /    \
//      L1.r    R1.r    ->     L1.b   R1.b
//     /                       /              
//    L2.r                   L2.r  
//描述：直接将 L1 R1 设为黑色 root 设为红色        
func Case1Handle(root *RBTree)*RBTree{
	root.SetColor(Red)
	root.LChild.SetColor(Black)	
	root.RChild.SetColor(Black)
	return root		
}

// 需要旋转的条件：子节点一红一黑,
//		 子孙同左红， 则祖右旋 (LL型)
//		 左子红，右孙红，则子左旋，再祖右旋  (LR型) -> (LL型)
//	     右子红，左孙红，则子右旋，在祖左旋	(RL型) -> (RR型)
//		 子孙同右红， 则祖左旋 (RR型)

// 子孙同右红，祖为红，子为黑， 再祖左旋 RR型左旋
func (rb *RBTree)RRRotation()*RBTree{
	rb.SetColor(Red)
	rb.RChild.SetColor(Black)
	bt , _ := RRRotation(rb).(*RBTree)
	return bt
}
// 右子红，左孙红，则子右旋，在祖左旋	(RL型) -> (RR型)
func (rb *RBTree)RLRotation()*RBTree{
	rb.RChild, _ = LLRotation(rb.RChild).(*RBTree)
	return rb.RRRotation()
}

// 子孙同左红，祖为红，子为黑， 再祖右旋 (LL型)
func (rb *RBTree)LLRotation()*RBTree{
	rb.SetColor(Red)
	rb.LChild.SetColor(Black)
	bt , _ := LLRotation(rb).(*RBTree)
	return bt
}

// 左子红，右孙红，则子左旋，再祖右旋  (LR型) -> (LL型)
func (rb *RBTree)LRRotation()*RBTree{
	rb.LChild, _ = RRRotation(rb.LChild).(*RBTree)
	return rb.LLRotation()
}


func CreateRBTree(data []interface{}){
	root := NewRBTree()
	root.SetColor(Black)
	root.Value = data[0]
	for _ ,v := range data[1:] {
		node := NewRBTree()
		node.Value = v
		root = root.Insert(node)
	}
	res := ""
	var dfs func(*RBTree)
	dfs = func (node *RBTree)  {
		if node == nil {
			return
		}
		res += node.String()
		dfs(node.LChild)
		dfs(node.RChild)
	}
	dfs(root)
	fmt.Println(res)
}